package cow

import (
	"fmt"
	"strconv"
	"strings"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

/*
创建二叉树
"1,2,3,4,5,6,7"
		1
	   / \
	  2   3
     / \ / \
    4  5 6  7

*代表为null
"1,2,3,4,*,*,7"
		1
	   / \
	  2   3
     / \ / \
    4  * *  7

算法思路：
通过广度优先遍历来创建二叉树
通过双指针，一个遍历第一层，一个遍历第二层，结束交换，再向下遍历
*/

func TreeCreater() *TreeNode {
	return new(TreeNode)
}

/*
CreateBinaryTree
广度优先创建二叉树
*/
func (t *TreeNode) CreateBinaryTree(treeStr string) *TreeNode {

	list := t.getList(treeStr)
	root := list[0]
	fmt.Println(PrintList(list))

	one := make([]*TreeNode, 0)
	two := make([]*TreeNode, 0)

	one = append(one, root)
	list = list[1:]

	for len(list) > 0 {
		node := list[0]
		if node == nil {
			list = list[1:]
		} else {
			one[0].Left = node
			two = append(two, node)
			list = list[1:]
		}

		if len(list) > 0 {
			node = list[0]
			if node == nil {
				list = list[1:]
			} else {
				one[0].Right = node
				two = append(two, node)
				list = list[1:]
			}
		}

		one = one[1:]
		if len(one) == 0 {
			one = two
			two = []*TreeNode{}
		}
	}

	return root
}

/*
打印二叉树
*/

func (t *TreeNode) PrintBinaryTree(root *TreeNode) string {
	list := make([]string, 0)
	t.deepTree(root, &list)
	fmt.Println(list)
	return ""
}

/*
WidthTree
广度遍历优先，打印二叉树为字符串
*/
func (t *TreeNode) WidthTree(root *TreeNode) {
	list := make([]*TreeNode, 0)
	one := make([]*TreeNode, 0)
	two := make([]*TreeNode, 0)

	if root == nil {
		return
	}

	one = append(one, root)
	list = append(list, root)

	for {

		if len(one) == 0 {
			one = two
			two = []*TreeNode{}
		}

		if len(one) == 0 && len(two) == 0 {
			break
		}

		node := one[0]
		if node == nil {
			list = append(list, node)
			one = one[1:]
			continue
		}

		if node.Left != nil {
			two = append(two, node.Left)
		}
		list = append(list, node.Left)

		if node.Right != nil {
			two = append(two, node.Right)
		}
		list = append(list, node.Right)

		one = one[1:]

		//time.Sleep(time.Second)
		//fmt.Println(PrintList(list))
	}

	fmt.Println(PrintList(list))
}

/*
深度优先遍历
*/
func (t *TreeNode) deepTree(root *TreeNode, list *[]string) {
	if root == nil {
		*list = append(*list, "*")
	} else {
		*list = append(*list, strconv.Itoa(root.Val))
		t.deepTree(root.Left, list)
		t.deepTree(root.Right, list)
	}
}

func (t *TreeNode) getList(treeStr string) []*TreeNode {
	list := make([]*TreeNode, 0)

	for _, item := range strings.Split(treeStr, ",") {
		if item == "*" {
			list = append(list, nil)
			continue
		}

		i, _ := strconv.Atoi(item)
		node := &TreeNode{
			Val: i,
		}
		list = append(list, node)
	}

	return list
}

func PrintList(list []*TreeNode) string {
	str := ""
	for _, item := range list {
		if item == nil {
			str += fmt.Sprintf("%s,", "*")
		} else {
			str += fmt.Sprintf("%d,", item.Val)
		}
	}
	//fmt.Println(str)
	return str
}
